__author__ = 'st316'
'''
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
dfs???
'''


class Solution:
    # @return a list of lists of integers
    def combine(self, n, k):
        if n == 0 or k == 0:
            return []
        if k == 1:
            return [[x] for x in xrange(1, n + 1)]
        r = []
        for x in xrange(1, n):
            tmp = self.combineX(n, x, k - 1)
            [z.insert(0, x) for z in tmp]
            r.extend(tmp)
        return r

    def combineX(self, n, x, k):
        if n == 0 or k == 0:
            return []
        if k == 1:
            return [[y] for y in xrange(x + 1, n + 1)]
        r = []
        for y in xrange(x + 1, n):
            tmp = self.combineX(n, y, k - 1)
            [z.insert(0, y) for z in tmp]
            r.extend(tmp)
        return r


if __name__ == '__main__':
    s = Solution()
    print s.combine(4, 2)

